\documentclass[twoside]{report}
\usepackage[pdftex]{graphicx}
\usepackage{amsmath}
\usepackage[utf8x]{inputenc}
\usepackage{mathtools}
\usepackage{amssymb}
\renewcommand{\bibname}{References}
\title{\Huge A Scalable Revocation Codecaps Query Service In Intrusion Network}
\date{}
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}
\begin{document}
\input{./title.tex}

%\clearpage
\begin{abstract}
In this thesis, we present a service, which provides clients with the ability to query fast for the status of the \emph{codecaps}. To ensure the timeliness of the \emph{codecaps}, a content distribution overlay network is constructed to disseminate the revoked \emph{codecaps}. Instead of requesting to the Certificate Authority, clients send Online Certificate Status Protocol (OCSP) requests to the service, and obtain the correct, more up-to-date status of the requesting \emph{codecap}. However, it is possible that some service nodes are Byzantine nodes. With \emph{Fireflies}, the list of revoked \emph{codecaps} can still be disseminated quickly to correct nodes. This thesis demonstrates that with Fireflies, the \emph{codecaps} revocation list is propagated to the correct nodes very fast, with high probability, and by OCSP, clients can retrieve real-time status of the \emph{codecap}.
\end{abstract}
\newpage\null\thispagestyle{empty}\newpage
\clearpage
\tableofcontents
\thispagestyle{empty}
\newpage\null\thispagestyle{empty}\newpage
\chapter{INTRODUCTION}
\pagenumbering{arabic}
\setcounter{page}{1}
The Revocation Codecaps Query Service is a scalable intrusion-tolerant distributed system that enables clients to send Online Certificate Status Protocol (OCSP) requests, to obtain the most recent status of the \emph{codecap}. In the service, \emph{Fireflies}\cite{fireflies} is in charge of forming a view of correct nodes. Based on the correct view, a content distribution component disseminates the list of revoked \emph{codecaps} in the service network. Online Certificate Status Protocol (OCSP) is used to enable clients to retrieve the real-time, correct status of the \emph{codecap}. 
\newline\indent With the advent of cloud computing, users' data is moved to the ``cloud''. Access control of the resources is one of the main concern in the cloud-based infrastructure. The easiest way is Access Control Lists (ACLs), which are created and modified manually by the system administrator. This approach will become inefficient if the cloud server is complex and at large scale, for instance, there are tens of thousands of users, and many different namespaces.
\newline\indent Another new approach is verifying the client's \emph{capabilities}. When a client accesses the resource, the service provider verifies only whether the request operation is listed in the client's \emph{capabilities}. In ACL model, each object has only one list, while in the capability model, the object has many separate lists. Consequently, the fine-grained characteristics of capabilities offer more flexible rights delegation and amplification.
\newline\indent \emph{Codecaps}\cite{codecaps} are the implementation of \emph{capabilities}, with a novel combination of X.509 certificate and JavaScript code fragment. \emph{Codecaps} offer rights delegation, confinement, and rights amplification. Revoking \emph{codecaps} should also be taken into consideration, because a \emph{codecap} is essentially a certificate, which can be revoked if the private key is compromised or the certificate is expired. Once a \emph{codecaps} is revoked, the revocation list should be propagated to other hosts as soon as possible.
\newline\indent Other than the Certificate Authority periodically pushing the revocation list to all hosts, a peer-to-peer (P2P) content distribution sub-service is constructed among all the hosts. After a CRL is generated on the Certificate Authority (CA), the CA picks a number of hosts to push the CRL, instead of pushing it to all the hosts. Then when the hosts, which receive the CRL, gossip the CRL to the other hosts. When a client wants to check out the validity of the certificate, the client requests to more than one \emph{OCSP responder}s to get the correct, most up-to-date status of the certificate. In order to disseminate the revocation list fast, the revocation list is distributed to all the hosts in the overlay network. However, in an intrusion network, some hosts do not forward the information by simply claiming they have not received the information. In other words, there may be Byzantine hosts in the network. \emph{Fireflies} is a group membership protocol, which ensures that the information is quickly propagated to the \emph{correct} hosts with high probability.
\section{Problem Definition}
The goal is to devise and construct a prototype of a scalable and reliable Internet service that minimize the time it takes from an revocation is issued to when it can efficiently block the invalidated \emph{codecaps}. Important non-functional aspects, i.e. reliability and scalability, must be considered in the prototype. This thesis shall provide a method for retrieving the status of the certificate, because essentially \emph{codecaps} are based on the standard X.509 public key certificates. In addition, this thesis should also take faulty nodes into consideration in that in intrusion network there are Byzantine nodes.
\section{Assumptions, Scope and Limitations}
The core of this thesis is to investigate how to disseminate revocation list to all the hosts in intrusion-tolerant networks. We will not focus on the delegation or the amplification of \emph{codecaps}. Since \emph{codecaps} are essentially X.509 certificates, in order to illustrate the interesting part, in this thesis, we built a prototype system that supports fast distribution of certificate revocation list in an intrusion-tolerant overlay network. Since \emph{Fireflies} supports both static and dynamic group membership, we choose the static group membership in our prototype system.
\newline\indent We simulate the Byzantine behavior as a number of nodes omit requests and do not forward the requests. The Denial-Of-Service (DoS) attack is outside of the scope of this thesis. In addition, we assume the private key of the Certificate Authority is kept securely.
\section{Methodology}
According to the final report of the ACM Task Force on the Core of Computer Science \cite{ACM}, the discipline of computing is divided into the three following paradigms:
\begin{itemize}
\item \emph{Theory} is rooted in mathematics and is followed in the development of a valid and coherent theory. The steps include: characterizing objects of study, hypothesizing possible relationships among them, determining if the relationships are true, and interpreting results.
\item \emph{Abstraction (Modelling)} is rooted in the experimental scientific method, which involves the formulation of an hypothesis, model construction, prediction, data collection, and results analysing.
\item \emph{Design} is rooted in engineering, which consist of requirements statement, specifications, design, implementation and test.
\end{itemize}
\indent The thesis is to demonstrate a proof of the concept, which addresses the problem described in problem definition. A prototype is built to validate the design. In addition, the prototype is also evaluated in the experiment to show its viability.
\section{Context}
This thesis is part of the information Access Disruption (iAD) centre for research. The iAD Centre targets core research for next generation precision, analytics and scale in the information access domain. Partially funded by the Research Council of Norway as a Centre for Research-based Innovation (SFI), iAD is directed by Microsoft Development Center (Norway) in collaboration with Accenture, Cornell University, University College Dublin, Dublin City University, BI Norwegian School of Management and the universities in Tromsø (UiT), Trondheim (NTNU) and Oslo (UiO).
\chapter{BACKGROUND}
There are two main approaches to control access to the object in the system \cite{security_in_computing}. As shown in Table ~\ref{access_control_matrix}, each row represents a subject, who has specific access right to the corresponding object. For instance, $USER\_A$ created the file $a.c$, so that this user has the right of \emph{owner}, as well as \emph{read} and \emph{write}. Each column represents an object, with the user list, as well as each user's access right. Each entry in Table ~\ref{access_control_matrix} is the set of access rights for that subject to that object. The row-wise's implementation is capabilities, and the column-wise's is ACLs.
\begin{table}[h]
\centering
\begin{tabular}{|l|c|c|c|c|c|}
\hline
~& \textbf{A.C}& \textbf{TEMP}& \textbf{B.SH}& \textbf{HELP.TXT}& \textbf{PRINTER}\\ \hline\hline
USER\_A& ORW& ORW& ORWX& R& W\\ \hline
USER\_B& R&     -&    -& R& W\\ \hline
USER\_C& RW&    -&    RW& R& W\\
\hline
\end{tabular}
\caption{Access Control Matrix}
\label{access_control_matrix}
\end{table}
\section{ACLs}
It is common that each object maintains a list of the access rights of users that want to access the object. The implementation is called Access Control Lists (ACLs), which are lists of permissions attached to objects. There is one list for each object, and the list shows all subjects who should have access to the object and what their access right is. One ACL corresponds one object. The ACL specifies which users or processes have access rights to the object, and what operations can be posed on the object. ACL is object-based, so that it is inconvenient for determining access rights to a specified user. In an access control list, if you want to change the operation rights or remove a user, the system administrator has to modify the ACL, which is cumbersome. If some users move in and out frequently, it will pose burden to system administrators.
\section{Capabilities}
Another approach is using capabilities. A capability is an unforgeable digital token, ticket, or key that gives the possessor permission to access an entity or object. When a client issues a request to the object, because capabilities are subject-based, the service provider is not interested in if the client is known to it, the service provider needs only to check if the capability is valid and whether the requested operation is listed in the capability. While each client carries a certificate, the client may have a few number of capabilities. When the client wants to request a resource, it hands over its certificate to the service provider. The certificate includes not only authentication information, but also authority information such as user roles or capabilities. The capabilities tend to change much faster than the user's identity. In addition, a capability allows the client to loan or delegate capabilities to other users, which is impossible in ACL. To assure transferring rights securely, extra security measures need to be taken. For the capability to offer solid protection, the ticket must be unforgeable.  To guarantee the certificate is genuine and has not been tempered with, it should be protected by means of a digital signature.
\newline\indent One possible access right to an object is transfer or delegation. A subject having this right can pass some types of access rights in capabilities to other subjects. For instance, in Table ~\ref{access_control_matrix}, $USER\_A$ is the owner of $b.sh$, then it can then pass (delegate) \emph{read} and \emph{write} operations to $USER\_C$.
\subsection{\emph{Codecaps}}
A \emph{codecap} (code capability) is a novel kind of capability. In capabilities, there is a predetermined collection of rights that can be turned on or off. By contrast, in \emph{codecap}, the set of rights is not predefined, but can be evolved as needed. It contains embedded code which can be executed to check if the entity has rightful access to the resource. For instance, we can create a time-range right function using JavaScript, defining that the service is available only from 8:00 AM to 5:00 PM no matter who you are.
\section{Certificate Revocation Lists (CRLs)}
\label{sec:crl}
A CRL is a list which contains the serial numbers of the revoked certificates. Certificates are not valid forever. Some mechanism is needed to handle the following events:
\begin{itemize}
\item The certificate is expired.
\item The private key is lost or compromised.
\item The information of the user is changed.
\item The owner of the certificate has left the organization \cite{pki}.
\end{itemize}
To deal with these events, the certificates needs to be revoked and the Certificate Authority (CA) needs to publish this revocation information, which is a list of revoked certificates. Revoking is the process of canceling an Secure Socket Layer (SSL) certificate, advising users of the certificate that it can no longer be considered to represent a trusted identity. This Certificate Revocation List (CRL) contains the serial numbers of certificates that have been revoked along with the date of revocation and a status identifying the reason for the revocation.
\newline\indent In public key infrastructure, public-key distribution takes place by means of public-key certificates. Such a certificate consists of a public key together with a string identifying the entity to which that key is associated.The public key and identifier have together been signed by a certification authority, and this signature has been placed on the certificate as well. Signing takes place by means of a private key that belongs to the certification authority. It is not secure for the certification authority to issue lifelong certificates. By publishing CRL, all other entities know that the certificates in CRL is not valid any more.
\newline\indent The main disadvantage of CRLs is that the CRL is downloaded at certain interval, which means the revoked certificate is still authenticated before the new CRL is reached. The lack of timeliness will result in security issues.
\section{Online Certificate Status Protocol (OCSP)}
OCSP is a simple, light-weighted request/response protocol. When validating a certificate, the OCSP client component constructs a a certificate status request, which mainly consists the serial number of the certificate,  the hash of the certificate issuer's distinguished name and the hash of the issuer's public key. As illustrated in Figure ~\ref{oscp}, the OCSP client submits the OCSP request to the OCSP responder through the Hypertext Transfer Protocol (HTTP). After receiving the request, the OCSP responder checks if the certificate is revoked. There are three possible status values: \emph{good} indicating the requested certificate is still valid, \emph{revoked} indicating the certificate has been revoked and is not trusted any more, \emph{unknown} indicating the certificate is not in the responder's revocation list. The response should be signed to ensure that this response is generated by a trusted responder and that it is not forged during transmission. Compared with the de-facto certificate revocation publication, that is CRLs, the newer OCSP mechanism offers the following advantages:
\begin{itemize}
\item More timely than CRLs.
\item Clients need not parse CRLs. Clients send only the identifications of the requested certificates.
\item Light-weighted. OCSP uses HTTP and attaches the request to the HTTP message. Furthermore, clients need not retrieve the complete (sometimes large) CRLs.
\end{itemize}
The client first checks if the certificate is on the Certificate Revocation List. This means that client has to contact the CA frequently, or the CA pushes the CRL periodically to clients, both of which will incur overhead. What's more, since the client contacts the CA within every fixed time period, the client does not get the list right away. Alternatively, Online Certificate Status Protocol offers a real-time mechanism to get the certificate status. It provides the client with the specific certificate status which the client request, with less network overhead.In the OCSP method, a client contacts a service running at the specified URL and asks the service whether a specific certificate has been revoked; again, the response is signed to prevent tampering. The response to the ``Is certificate $<$XXX$>$ revoked'' query is typically much smaller than downloading an entire CRL file. If each OCSP request does not complete in less than 15 seconds, it times out. OCSP has the primary benefit of requiring less network bandwidth, enabling real-time and near real-time status checks for high volume or high value operations.Figure ~\ref{oscp} describes the simplified OCSP flow.
\begin{figure}[h]
\centering
\includegraphics[scale=1]{./eps/ocsp.eps}
\caption{Simple OCSP flow}
\label{oscp}
\end{figure}
\section{\emph{Fireflies}}
\emph{Fireflies} is a group membership protocol, which can provide correct members with a current view of live members. While \emph{Fireflies} can not distinguish Byzantine members, it is a probabilistic protocol and ensures that the member can get correct reply with high probability. Based on a secure collision-resistant hash function, a mesh is generated to ensure that all the correct members are well connected, but not fully-connected. To fight Byzantine members, the members use the pinging to detect abnormal cases (i.e. a node crashed or a node does not reply). In addition, a ring structure is generated on each member so that each node can only communicate with its \emph{successor}s and \emph{predecessor}s. This restriction helps reduce the traffic crated by Byzantine nodes.
\begin{figure}[h]
\centering
\includegraphics[scale=1]{./eps/mesh.eps}
%\numberwithin{figure}{section}
\caption{Convert Rings to Mesh}
\label{ring_2_mesh}
\end{figure}
\newline\indent In the overlay network, every member, which is instrumented with \emph{Fireflies} protocol, generates the same number of rings. In each ring, the member will have some \emph{successor}s and \emph{predecessor}s. For example, in Figure ~\ref{ring_2_mesh}, there are five nodes ($A$, $B$, $C$, $D$ and $E$) in the network overlay. They are organized on several rings, and the position of each member is dictated by a hash function. Meanwhile, it is possible the ordering of the nodes on each ring is different. Each member has the same number of \emph{successor}s and \emph{predecessor}s as the ring is created as a circular address space. For instance, the successors of $A$ are $B$ and $C$, and its predecessors are $C$ and $D$. Even though there is a 2-ring view on each node, there still only one $A$ node in the network, not two. The reason for generating these rings it that a member can gossip only with its \emph{successor}s, and it can be \emph{accused} by only its \emph{predecessor}s. For example, $A$ can gossip only with $B$ and $C$. Only $C$ and $D$ can send \emph{accusation} to $A$. If $A$ is a Byzantine node, without this rules, it can create many repeat \emph{accusation}s to every node in the network, which will consequently incur large amounts of traffic. In order to better illustrate the member relationship, the mesh is represented by a number of rings. $A$, $B$, $C$, $D$ and $E$ are connected, but not fully connected as fully-connection will not scale.
\newline\indent Each member has a state, which is either \emph{correct}, \emph{stopped}, and \emph{Byzantine}. \emph{Correct} nodes are those who execute the protocol faithfully. \emph{Stooped} nodes do not respond to any communication. The behaviors of Byzantine nodes are not bounded. Because \emph{Fireflies} can not distinguish Byzantine nodes in general, \emph{correct} and Byzantine nodes are both live nodes as opposed to \emph{stopped} nodes. There are mainly two individual information exchanging parts. One is pinging which is used to detect the liveness of the member. The other one is gossiping \emph{note}s and \emph{accusations} to ensure all \emph{correct} nodes are connected.  A note is a triplet (\emph{pub\_cert}, \emph{version\_number}, \emph{bitmap}). \emph{bitmap} is used to determine which predecessors are allowed to accuse the member. An accusation (\emph{note}, \emph{ring\_num}, \emph{accuser}). For instance $A$ monitors $C$ by sending a ``ping'' message in a time period, after which $A$ waits for $C$'s \emph{rebuttal}. The interval is calculated dynamically based on the probability of message loss and some other factors. If $C$ responds with a ``pong'' message, it means that $C$ is live, no matter $C$ is \emph{correct} or Byzantine. Consequently $A$ removes the corresponding timer. On the other hand, if $A$ does not receive the response from $C$ during the time period, which means $C$ is \emph{stopped}, $A$ issues an \emph{accusation} and gossips \emph{accusation} to all its \emph{successor}s. It is possible that each member will have the full membership by gossiping only a set of members \cite{partial_gossip}. Assume the probability of two nodes being connected is $p_n$ = ($\log$n+c+\emph{o}(1)), the probability of the graph being connected is $\exp$($-$$\exp$($-$c)) (c is a constant) \cite{equation}. Let $P_byz$ be the probability that a live member is a Byzantine node, \emph{n} the number of correct nodes in the view, \emph{N} the number of live nodes, to ensure that the correct nodes are connected with probability $\varphi$, \emph{k} is calculated by: \cite{fireflies} \[\mathit{k} \geqslant \frac{1}{2\left ( 1-P_{byz} \right )}\cdot \left ( \log \frac{-N\left ( 1-P_{byz} \right )}{\log \varphi } +\mathit{o}\left ( 1 \right )\right )\]
\newline\indent There are \emph{k} rings on each node, and likewise each node has \emph{k} successors (including duplicated successors). By gossiping the \emph{notes} between neighbors, a member will learn to know the full membership. Each correct member has a \emph{view}, which is constituted by the correct members. Each node also has a set of \emph{neighbors}, which are the member's correct \emph{successor}s. Thus a node's \emph{neighbor}s are a set of its \emph{view}. For example, if $A$ does not receive response from $C$ during the time period, $A$ creates an accusation and gossips this accusation to its successors $B$. Meanwhile, $A$ also has a timer to wait for $C$'s rebuttal. After receiving, $B$ checks this accusation is valid. If it is valid, $B$ gossips the accusation to its successors. When $C$ receives the accusation about itself, firstly, it checks its \emph{bitmap} if $A$ is allowed to accuse it. If it is allowed, $C$ can issue a \emph{rebuttal} and gossip it to show it is still live. After the time is up, all the correct members will remove $C$ from their view.
\chapter{REQUIREMENT}
In an intrusion network, there may be some faulty nodes, for example, some nodes are running fairly slowly because of low hardware configuration, limited memory, and there are also some Byzantine nodes that do not forward anything by pretending running slowly. The requirement is to provide a scalable service by which clients can obtain the correct status of a \emph{codecap} very fast under certain intrusion-tolerant level. For example, multiple CAs issue certificates to the corresponding nodes, some of which are service providers. In order to protect the raw data, or to better control the access rights, service providers delegate some specific \emph{codecaps} to the client. When the service provider's codecap is revoked, and after a client requests the status of this codecap, it is required that the client can get the correct status of the codecap. In this case, the up-to-date status is revoked.
\begin{figure}[h]
\centering
\includegraphics[scale=1]{./eps/design_new.eps}
%\numberwithin{figure}{section}
\caption{Requirement Definition}
\label{requirement_definition}
\end{figure}
\newline\indent In Figure ~\ref{requirement_definition}, there is a Root CA. $CA$ issues certificates to node $A$, node $B$ node $C$ and node $D$. We assume $B$ provides online photo service to client $c_1$. $B$ delegates two types of capabilities to $c_1$, read and write only in daytime (8:00 AM - 5:00 PM). If $c_1$ would like to access the resource in $B$, $c_1$ and $B$ should be mutually authenticated. There may be Byzantine nodes in the overlay network. At some time, $B$'s certificate is revoked by $CA_1$, after that, if $c_1$ would like to access his online photos in $B$, $c_1$ will first send OCSP request to more than one node in the network, querying for $B$'s certificate status. $c_1$ should the correct response, which indicates $B$'s certificate is on the revocation list. Consequently, $c_1$ knows that $B$ is no longer trusted.
\newline\indent We outline the main requirements as below:
\begin{itemize}
\item Clients can obtain the correct status of the requested \emph{codecap} fast.
\item The service can tolerate Byzantine nodes on certain level.
\item The service should scale up to thousands of nodes.
\end{itemize}
\chapter{DESIGN AND IMPLEMENTATION}
Since a \emph{codecap} is a combination of a certificate and embedding JavaScript code, for simplicity sake, a \emph{codecap} is considered as a certificate in the design. As described in Section~\ref{sec:crl}, the CRLs, which are pushed periodically to all the clients by the CAs, are not real-time. In order for the clients to get the up-to-date status of the requested certificate, the OCSP protocol is chosen to allow clients to query for the status timely. However, the CAs will be overloaded when all the clients send OCSP requests to them. This approach also does not scale. To address the scalability problem, a peer-to-peer content distribution overlay is introduced. The CA pushes the created CRLs to a set of nodes running the service. Then the CRLs are distributed to all the nodes on the overlay. Thus all the nodes have the updated information of the CRLs. Instead of requesting CAs directly, clients send OCSP requests to a set of nodes to obtain the status of the certificate. As is stated in the requirements, there may be Byzantine nodes in the network. Fireflies is used to offer correct nodes with the view of live nodes and meanwhile to form a mesh for communication with correct nodes. Based on the membership of correct nodes, on top of \emph{Fireflies}, a distributor can disseminate the CRLs to the other correct nodes. Therefore, the design goals of the codecaps revocation query service are:
\begin{itemize}
\item The CRLs generated by the CAs should be propagated fast to the nodes in the overlay network.
\item Each node should be able to reply clients by OCSP.
\item Intrusion-tolerance is handled by \emph{Fireflies}.
\end{itemize}
\begin{figure}[h]
\centering
\includegraphics[scale=1]{./eps/design.eps}
%\numberwithin{figure}{section}
\caption{Design}
\label{design}
\end{figure}
Figure ~\ref{design} shows the high-level view of the revocation query service's design. The service exposes as a OCSP responder to the clients. OCSP Responder is the uppermost layer in the design of the service. The middle layer is \emph{distributor} layer. This layer receives CRLs either from CAs or other nodes in the  revocation query service network. When the distributor disseminates the CRLs to other nodes. The nodes are chosen from the correct nodes, which are maintained by the bottom layer \emph{Fireflies} Agent. To deal with Byzantine nodes in the service network, CAs send CRLs to a number of nodes to make sure at lease one correct node receives the CRL. For the same reason, one client is required to send the OCSP request to a set of nodes to ensure the client will receive at least one correct response.
\begin{itemize}
\item \emph{Fireflies} Agent: A membership of correct nodes is constructed by \emph{Fireflies} agent on each node. It uses accusations to remove the stopped nodes from the view and uses ring structure to prevent Byzantine nodes from accusing many nodes.
\item OCSP Responder: It acts as a server to clients and responds them by the format of the OCSP protocol.
\item \emph{Distributor}: It receives the updated CRLs from CAs or other nodes, and periodically distributes the CRLs to other correct nodes.
\end{itemize}
\section{Implementation issues}
Since OCSP (RFC 2560) is already on the Internet standards track, we can use an on-shelf OCSP responder library. As for the distributor layer, if it receives CRLs from a plain socket, the distributor extracts the \emph{X509v3 CRL Number} from the CRL, and compares the \emph{X509v3 CRL Number} with the current one. If the number is greater, which means the CRL is more up-to-date, the current CRL is replaced by the received CRL. After that, the distributor picks one node from the correct view, and sends the CRL to it. As shown on the left part of Figure ~\ref{pseudocode}, the sending thread periodically picks one node from its view which is only writable to \emph{Fireflies} Agent. If the current CRL has not been sent to the node by comparing the CRL number with the one which is sent last time, then the current CRL is sent to the node.
\begin{figure}[h]
\centering
\includegraphics[scale=1]{./eps/pseudocode.eps}
%\numberwithin{figure}{section}
\caption{pseudocode of receiving thread and timing sending thread}
\label{pseudocode}
\end{figure}
\chapter{EVALUATION}
Our prototype implementation is going to be written in JAVA. The implementation will use TCP for both CRL distribution, TCP for gossip in \emph{Fireflies} Agent, UDP for pinging in \emph{Fireflies} Agent, and HTTP for OCSP. After setting the configuration parameters in Table ~\ref{configuration}, a Public Key Infrastructure is constructed by command lines provided by OpenSSL toolkit.\footnote{http://www.openssl.org/} A self-signed CA, the certificates of all the nodes, as well as CRLs, are also generated by OpenSSL toolkit. When each node is bootstrapping, it reads from a \emph{memberlist} file which consists of all the members' information (Public IP + Port) on each line. Since the membership is handled by \emph{Fireflies}, in the experiment, we will use the static membership. At the beginning, no CRL is generated by the CA. Each node in the service network gossips its \emph{note} to accuse the stopped nodes if any. The \emph{Fireflies} Agent running on each node tries to form a correct mesh. Meanwhile, a CRL is generated manually by OpenSSL command lines, and the CRL is sent to a set of nodes, then the revocation certificate query service starts to distribute the CRL in the network. If some clients are requesting to obtain the status of the certificate, which was revoked by the CA, We believe that with high probability, clients are able to obtain the correct status of a requested certificate fast.
\begin{table}[h]
\centering
\begin{tabular}{|l|l|}
\hline
\textbf{Parameter}& \textbf{Description}\\ \hline\hline
$P_{byz}$& Probability that a live member is Byzantine\\ \hline
N& Number of live members\\ \hline
$\Delta$& Time to distributed a membership event\\ \hline
$T_{distribution}$& Time to distributed a CRL\\ \hline
$T_{ping}$& Pinging interval\\ \hline
$T_{gossip}$& Gossip interval\\ \hline
$\varphi$& Probability of having a correct mesh\\
\hline
\end{tabular}
\caption{Configuration}
\label{configuration}
\end{table}
\chapter{RELATED WORK}
Fireflies is used as a building block in \cite{firepatch} and \cite{resilient_mirrors}, which offers an intrusion-tolerant mechanism to distribute software updates. In \cite{firepatch} and \cite{resilient_mirrors}, because the size of the content is large (a couple of Megabytes), a two-phase dissemination protocol is employed to make the \emph{window of vulnerability} (WOV) independent of content size. Our service employs a simple gossip approach in the \emph{distributor} layer because of the small size of CRLs. The size is on an order of kilobyte. Periodically, one node pushes a CRL to another node if the sending node finds the CRL is more up-to-date than the CRL that was previously sent. In order for the \emph{Fireflies} Agent to reduce the gossip traffic, instead of sending the original message, a hash of the message is sent, which is as same as in \cite{chainsaw}.
\newline\indent There are a lot of application-layer content distribution mechanisms. The main arguement is mesh versus tree-based. The shortcoming of \cite{splitstream} and \cite{bullet} is that the tree-based mechanism is more fragile that mesh, because if a node crashes all its children node will lose connection. In contrast, mesh is more robust. Future work should be done to choose another more efficient CRL gossiping to reduce the network overhead.
\chapter{CONCLUSION}
We have described a scalable revocation certificate query service, which is a combination of current techniques, which are \emph{Fireflies} and OCSP, to provide a intrusion-tolerant service for clients to query for the correct, up-to-date status of the requesting \emph{codecap}. The gossip for construct the view of correct members and for distributing CRLs are based on mesh, which achieves the scalability. After revoking a \emph{codecap}, that is a certificate, the revocation list can be consulted by Online Certificate Status Protocol (OCSP), from clients to service nodes. The advantage of OCSP over Certificate Revocation Lists (CRLs) is that the Certificate Authority is relieved from pushing the revocation list to every host. In addition, the revocation list is more real-time. A peer-to-peer content distribution network is constructed to disseminate the CRLs among the service nodes.
\newpage
\bibliography{codecap_revocation}{}
\bibliographystyle{unsrt}
\end{document}
